TNotes.leetcode

Appearance

0214. 最短回文串【困难】

0214. 最短回文串【困难】 ​

1. 📝 题目描述 ​

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

回文串是向前和向后读都相同的字符串。

示例 1：

txt
输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

txt
输入：s = "abcd"
输出："dcbabcd"

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 仅由小写英文字母组成

2. 🎯 s.1 - KMP + 最长回文前缀 ​

c
static char* copyString(const char* s, int n) {
    char* copy = (char*)malloc((n + 1) * sizeof(char));
    memcpy(copy, s, n);
    copy[n] = '\0';
    return copy;
}

char* shortestPalindrome(char* s) {
    int n = strlen(s);
    if (n < 2)
        return copyString(s, n);

    char* reversed = (char*)malloc((n + 1) * sizeof(char));
    for (int i = 0; i < n; i++)
        reversed[i] = s[n - 1 - i];
    reversed[n] = '\0';

    int combinedLen = 2 * n + 1;
    char* combined = (char*)malloc((combinedLen + 1) * sizeof(char));
    memcpy(combined, s, n);
    combined[n] = '#';
    memcpy(combined + n + 1, reversed, n);
    combined[combinedLen] = '\0';

    int* lps = (int*)calloc(combinedLen, sizeof(int));
    for (int i = 1; i < combinedLen; i++) {
        int j = lps[i - 1];
        while (j > 0 && combined[i] != combined[j])
            j = lps[j - 1];
        if (combined[i] == combined[j])
            j++;
        lps[i] = j;
    }

    int longestPrefixLength = lps[combinedLen - 1];
    int suffixLen = n - longestPrefixLength;
    char* result = (char*)malloc((n + suffixLen + 1) * sizeof(char));

    for (int i = 0; i < suffixLen; i++)
        result[i] = s[n - 1 - i];
    memcpy(result + suffixLen, s, n);
    result[n + suffixLen] = '\0';

    free(reversed);
    free(combined);
    free(lps);
    return result;
}
js
/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function (s) {
  const n = s.length

  if (n < 2) return s

  const reversed = s.split('').reverse().join('')
  const combined = s + '#' + reversed
  const lps = new Array(combined.length).fill(0)

  for (let i = 1; i < combined.length; i++) {
    let j = lps[i - 1]

    while (j > 0 && combined[i] !== combined[j]) j = lps[j - 1]
    if (combined[i] === combined[j]) j++

    lps[i] = j
  }

  const longestPrefixLength = lps[combined.length - 1]
  return s.slice(longestPrefixLength).split('').reverse().join('') + s
}
py
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        reversed_s = s[::-1]
        combined = s + "#" + reversed_s
        lps = [0] * len(combined)

        for i in range(1, len(combined)):
            j = lps[i - 1]
            while j > 0 and combined[i] != combined[j]:
                j = lps[j - 1]
            if combined[i] == combined[j]:
                j += 1
            lps[i] = j

        longest_prefix_length = lps[-1]
        return s[longest_prefix_length:][::-1] + s
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度，构造反转串、计算前缀函数和拼接答案都只需线性扫描一次
  • 空间复杂度：O(n)，需要额外存储反转串、拼接串和前缀函数数组

算法思路：

  • 目标是尽量保留原串开头那一段已经满足回文的部分，所以问题可以转化为求 s 的最长回文前缀
  • 令 rev = reverse(s)，构造字符串 t = s + '#' + rev，其中分隔符 # 用来避免前后两段发生跨边界的伪匹配（防止前后两部分的前缀/后缀互相“串通”）
  • 对 t 计算 KMP 的前缀函数，lps[t.length - 1] 就是 s 的最长回文前缀长度，因为它同时表示 s 的前缀和 rev 的后缀的最长匹配长度
  • 如果 s 的前 k 个字符既是 s 的前缀、又是 reversed 的后缀，说明：s[0..k-1] = reversed[末尾-(k-1)..末尾]，即 s 的前 k 个字符反转后等于自身 => 这正是回文的定义
  • 找到这个长度后，剩余的后缀 s[k...] 不是回文前缀的一部分，只需将它反转后补到最前面，再拼上原串即可得到最短回文串

3. 🔗 引用 ​

Discussions